home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / amiga / fractal / fr_notes.lha / gamaze.asc < prev   
Encoding:
Text File  |  1991-04-07  |  6.5 KB  |  322 lines
  1. _GENETIC ALGORITHMS_
  2. by Mike Morrow
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7. /*** GASystem -- Mike Morrow -- Objective function **/
  8.  
  9. #include "ga.h"
  10.  
  11. void objinit()
  12. {
  13. }
  14.  
  15. FIT_TYPE objective(s, len)
  16. SEQ s;
  17. int len;
  18. {
  19.     FIT_TYPE n;
  20.     unsigned int i;
  21.     static char tgt[] = "HELLOTHERE";
  22.     
  23.     n = 0;
  24.     for(i = 0; i < len && i < sizeof tgt - 1; i++)
  25.         if(tgt[i] == s[i])
  26.             n++;
  27.     
  28.     return n;
  29. }
  30.  
  31. void objshow(s, len, fitness)
  32. SEQ s;
  33. int len;
  34. FIT_TYPE fitness;
  35. {
  36.     printf("%d        ", fitness);
  37.     while(len--) printf(" %c", *s++);
  38.     puts("");
  39. }
  40.  
  41. void objdumpdone()
  42. {
  43.  
  44. }
  45.  
  46.  
  47. [LISTING TWO]
  48.  
  49. /*** GASystem -- Mike Morrow -- Objective function.  Evaluates a set of 
  50. * directions as applied to a maze. The closer the set of directions gets to 
  51. * the end of the maze, the higher the fitness of that set of directions.
  52. **/
  53.  
  54. #include "ga.h"
  55. #include <stdio.h>
  56.  
  57. /** A set of directions is made up of the following **/
  58. #define NORTH   0
  59. #define    EAST    1
  60. #define WEST    2
  61. #define SOUTH    3
  62.  
  63. /** Define the maze **/
  64. #if MSDOS
  65. #define BLOCK    (char) 178        /* block char on PC */
  66. #define SPACE    ' '
  67. #else
  68. #define BLOCK    '@'
  69. #define SPACE    ' '
  70. #endif
  71.  
  72. #define    _            BLOCK,
  73. #define A            SPACE,
  74.  
  75. #define    MAZEX    17
  76. #define MAZEY    13
  77.  
  78. typedef char MAZE[MAZEY][MAZEX];
  79. typedef char DISPLINE[80];
  80.  
  81. static CONST MAZE maze =
  82. {
  83.     _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
  84.     _ A A A A A A A _ _ _ _ _ _ _ A _
  85.     _ A _ _ A _ _ _ _ _ A A _ _ _ A _
  86.     _ A _ _ A A A A A A A _ _ A A A _
  87.     _ A _ _ A _ _ _ A _ _ _ _ A _ _ _
  88.     _ A _ _ _ _ _ _ A A A _ _ A _ A _
  89.     _ A _ _ A _ _ _ _ _ _ _ _ A _ A _
  90.     _ A A A A A A _ _ _ A A A A _ A _
  91.     _ _ _ _ A _ _ _ A _ A _ _ A _ A _
  92.     _ A _ _ A _ A A A _ A A _ A A A _
  93.     _ A A A A _ _ _ A _ _ _ _ _ _ A _
  94.     _ A _ _ A A A A A A A A A A A A _
  95.     _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
  96. };
  97.  
  98. /** Maze runners start at this point in the maze **/
  99. #define MAZESTARTX    10
  100. #define MAZESTARTY    11
  101.  
  102. /** Maze runners' goal is this point in the maze **/
  103. #define MAZEENDX    7
  104. #define MAZEENDY    1
  105.  
  106. /** How far from the MAZEEND is this set of points (x, y)? **/
  107. #define DIST(x, y) ((MAZEENDX - x) * (MAZEENDX - x) + (MAZEENDY - y) 
  108.                                                              * (MAZEENDY - y))
  109.  
  110. /** What is the longest distance in a maze this size? **/
  111. #define MAXDIST ((MAZEX * MAZEX) + (MAZEY * MAZEY))
  112.  
  113.  
  114.  
  115.  
  116. #if __STDC__ || __ZTC__
  117. static int mazerun(SEQ s, int len, unsigned int *xp, unsigned int *yp);
  118. static int xroads(int x, int y);
  119. #else
  120. static int mazerun();
  121. static int xroads();
  122. #endif
  123.  
  124. void objinit()
  125. {
  126.     char exebuff[80];
  127.     
  128.        /** set parameters.  High allele should be SOUTH, low allele 
  129.        * should be NORTH. **/
  130.     sprintf(exebuff, "HIA = %d", SOUTH);
  131.     exec(exebuff);
  132.  
  133.     sprintf(exebuff, "LOWA = %d", NORTH);
  134.     exec(exebuff);
  135.  
  136.         /** For starters, give a gene this many elements. User may want to 
  137.         * experiment with this parameter anyway. **/
  138.     sprintf(exebuff, "LEN = 15");
  139.     exec(exebuff);
  140. }
  141.  
  142. /*** This function evaluates a gene's sequence of directions. It returns
  143. * a fitness value. ***/
  144. FIT_TYPE objective(s, len)
  145. SEQ s;
  146. int len;
  147. {
  148.     FIT_TYPE dist;
  149.     unsigned int x, y;
  150.     int n_moves;
  151.  
  152.    /** Run through maze using directions in s. x and y will get final position 
  153.    * we reach. n_moves will get number of moves it took to get there. **/
  154.     n_moves = mazerun(s, len, &x, &y);
  155.     
  156.     /** The fitness of that path through maze is distance from MAZEEND.**/
  157.     dist = DIST(x, y);
  158.     
  159.     /** Convert: lower distances imply higher fitness value. **/
  160.     dist = (FIT_TYPE)MAXDIST - dist;
  161.     
  162.     /** Scale down result.     **/
  163.     dist = (dist * dist) >> 12;
  164.     
  165.     /** Plus a bonus for brevity.     **/
  166.     dist += 5 * (FIT_TYPE) (len - n_moves);
  167.  
  168.     return dist;
  169. }
  170.  
  171. static CONST char i_to_c[] = "NEWS";
  172.  
  173. #define N_PER_DISP_BLOCK    5
  174.  
  175. static DISPLINE displines[N_PER_DISP_BLOCK];
  176. static int n_lines = 0;
  177. static MAZE disp_maze;
  178.  
  179. void objshow(s, len, fitness)
  180. SEQ s;
  181. int len;
  182. FIT_TYPE fitness;
  183. {
  184.     unsigned int x, y;
  185.     int n_moves;
  186.     DISPLINE buff;
  187.     
  188.     if(! n_lines)
  189.         memcpy(disp_maze, maze, sizeof maze);
  190.         
  191.     n_moves = mazerun(s, len, &x, &y);
  192.     
  193.     disp_maze[y][x] = '0' + n_lines;
  194.     
  195.     sprintf(displines[n_lines], "%6d    ", fitness);
  196.     while(len--)
  197.     {
  198.         if(*s > SOUTH)
  199.             sprintf(buff, " %d!", *s++);
  200.         else
  201.             sprintf(buff, " %c", i_to_c[*s++]);
  202.         strcat(displines[n_lines], buff);
  203.     }
  204.  
  205.     sprintf(buff, " : (%2d, %2d); %2d moves", x, y, n_moves);
  206.     strcat(displines[n_lines], buff);
  207.     
  208.     n_lines++;
  209.     if(n_lines == N_PER_DISP_BLOCK)
  210.         objdumpdone();
  211. }
  212.  
  213. void objdumpdone()
  214. {
  215.     unsigned int i, x, y;
  216.     
  217.     if(! n_lines)
  218.         return ;
  219.     
  220.     for(i = 0; i < n_lines; i++)
  221.     {
  222.         printf("%d)    %s\n", i, displines[i]);
  223.     }
  224.     
  225.     puts("");
  226.     for(y = 0; y < MAZEY; y++)
  227.     {
  228.         printf("        ");
  229.         for(x = 0; x < MAZEX; x++)
  230.         {
  231.                 putchar(disp_maze[y][x]);
  232.         }
  233.         puts("");
  234.     }
  235.     n_lines = 0;
  236.     puts("\n\n");
  237. }
  238.  
  239. /** Run through maze with directions given in s.  *xp and *yp are set to final 
  240. * coords that we end up with. This function returns number of moves it took to
  241. * run maze. It will terminate when moves in s are used up, or when we arrive 
  242. * at the end of maze. **/
  243. static int mazerun(s, len, xp, yp)
  244. SEQ s;
  245. int len;
  246. unsigned int *xp, *yp;
  247. {
  248.     register int x, y;
  249.     register SEQ dirs;
  250.     int n_moves;
  251.  
  252.     
  253.     x = MAZESTARTX;
  254.     y = MAZESTARTY;
  255.     dirs = s;
  256.     n_moves = 0;
  257.     
  258.         while(len-- && ! (x == MAZEENDX && y == MAZEENDY))
  259.         {
  260.                 switch(*dirs++)
  261.                 {
  262.                         case NORTH:
  263.                              while(maze[y - 1][x] == SPACE)
  264.                              {
  265.                                 y--;
  266.                                 if(xroads(x, y))
  267.                                 break;
  268.                               }
  269.                          break;
  270.                 
  271.             case EAST:
  272.                 while(maze[y][x + 1] == SPACE)
  273.                 {
  274.                     x++;
  275.                     if(xroads(x, y))
  276.                         break;
  277.                 }    
  278.                 break;
  279.                 
  280.             case WEST:
  281.                 while(maze[y][x - 1] == SPACE)
  282.                 {
  283.                     x--;
  284.                     if(xroads(x, y))
  285.                         break;
  286.                 }    
  287.                 break;
  288.                 
  289.             case SOUTH:
  290.                 while(maze[y + 1][x] == SPACE)
  291.                 {
  292.                     y++;
  293.                     if(xroads(x, y))
  294.                         break;
  295.                 }
  296.                 break;
  297.                 
  298.         default:
  299.          printf("Error in objective(), got allele = %d!", *(dirs - 1));
  300.                 break;
  301.         }
  302.         n_moves++;
  303.     }
  304.     *xp = x;
  305.     *yp = y;
  306.     
  307.     return n_moves;
  308. }
  309.  
  310. /** If this is a cross roads in maze, i.e. there are more than two exits 
  311. * from the current cell, then return TRUE. **/
  312. static int xroads(x, y)
  313. int x, y;
  314. {
  315.     char exits;
  316.     
  317.     exits = (maze[y][x+1] != SPACE) + (maze[y][x-1] != SPACE) +
  318.         (maze[y+1][x] != SPACE) + (maze[y-1][x] != SPACE);
  319.     return exits < 2;
  320. }
  321.  
  322.